from collections import defaultdict
import heapq
from typing import List


class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: list[int], capital: List[int]) -> int:
        p = []
        heapq.heapify(p)

        c2p = defaultdict(list)  # 某个成本对应的下标
        for i in range(len(profits)):
            c2p[capital[i]].append(i)
        prev_w =-1
        for _ in range(k):
            # 找到目前成本能进行的项目
            for c in range(prev_w+1,w+1):
                profit_indexs = c2p[c]
                for index in profit_indexs:
                    heapq.heappush(p,-profits[index])
            # 取出最大的利润项目
            if p:
                maxprofit = -heapq.heappop(p)
                prev_w = w
                w += maxprofit
            else:
                return w
        return w

if __name__ == "__main__":
    s = Solution()
    r = s.findMaximizedCapital(10,0,[1,2,3],[0,1,2])
    print(r)